class Solution:
    def rob2(self, nums: List[int]) -> int:
        n = len(nums)
        @cache
        def dfs(i):
            if i < 0:
                return 0
            
            res = max(dfs(i-1),dfs(i-2)+nums[i])
            return res
        return dfs(n-1)
    def rob(self, nums: List[int]) -> int:
        
        return max(nums[0] + self.rob2(nums[2:-1]),self.rob2(nums[1:]))


class Solution:
    def rob2(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for x in nums:
            f0,f1 = f1,max(f1,f0+x)
        return f1
    def rob(self, nums: List[int]) -> int:
        return max(nums[0] + self.rob2(nums[2:-1]),self.rob2(nums[1:]))